// 分而治之 - （归并，排序）
// 二分搜索
// 分解 - 计算mid 并搜索数组较小或者较大的一半
// 解决 - 在较小或者较大的那部分当中搜索
// 合并 - 这步不需要，因为直接返回了索引

export function binarySearch(array, value, compareFn = defaultCompare) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high, compareFn)
}

function binarySearchRecursive(array, value, low, high, compareFn = defaultCompare) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];
        if (compareFn(element, value) === Compare.LESS_THAN) {
            return binarySearchRecursive(array, value, mid + 1, high, compareFn)
        } else if (compareFn(element, value) === Compare.BIGGER_THAN) {
            return binarySearchRecursive(array, value, low, mid - 1, compareFn);
        } else {
            return mid;
        }
    }
    return DO_NOT_EXIST;
}

// 动态规划
// 1. 定义子问题
// 2. 实现要反复执行的来解决子问题的部分(这一步参考递归)
// 3. 识别并求解出基线条件

// 背包问题：给出一组项，各自有值和容量，目标是找出总值最大的项的集合，这个问题的限制在于总容量必须小于等于背包的容量

// 整数背包问题 - 组合优化问题
// 给定一个固定大小能够携带重量为W的背包，以及一组有价值和重量的物品，找出一个最佳解决方案，使得装入背包的物品总重量不超过W，且总价值最大
//  物品 重量 价值
//  1   2    3
//  2   3    4
//  3   4    5

function knapSack(capacity, weights, values, n) {
    const kS = []; // ks[n+1][capacity+1]
    for (let i = 0; i <= n; i++) {
        kS[i] = [];
    }
    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            if (i === 0 || w === 0) {
                kS[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                const a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
                const b = kS[i - 1][w]
                kS[i][w] = a > b ? a : b;
            } else {
                kS[i][w] = kS[i - 1][w]
            }
        }
    }
    findValues(n, capacity, kS, weights, values)
    return kS[n][capacity]
}

function findValues(n, capacity, kS, weights, values) {
    let i = n;
    let k = capacity;
    while (i > 0 && k > 0) {
        if (kS[i][k] !== kS[i - 1][k]) {
            i--;
            k -= kS[i - 1][k];
        } else {
            i--
        }
    }
}

// 最长公共子序列(LCS)：找出一组序列的最长公共子序列(可由另一序列删除元素但不改变余下元素顺序而得到)
// 找出两个字符串序列的最长子序列的长度。最长子序列指的是在两个字符串序列中以相同顺序出现，但是不要求连续(非字符串子串)的字符串序列
// string1: acbaed
// string2: abcadf
// LCS -> 长度为4的acad

function lcs(wordX, wordY) {
    const m = wordX.length;
    const n = wordY.length;
    const l = []
    const solution = [];

    for (let i = 0; i <= m; i++) {
        l[i] = [];
        solution[i] = [];
        for (let j = 0; j <= n; j++) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }

    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i === 0 || j === 0) {
                l[i][j] = 0;
            } else if (wordX[i - 1] === wordY[j - 1]) {
                l[i][j] = l[i-1][j-1] + 1;
                solution[i][j] = 'diagonal';
            } else {
                const a = l[i-1][j];
                const b = l[i][j-1];
                l[i][j] = a > b ? a : b
                solution[i][j] = (l[i][j] === l[i-1][j]) ? 'top' : 'left'
            }
        }
    }
    printSolution(solution, wordX, wordY, m, n);
    return l[m][n];
}

function printSolution(solution, wordX, wordY, m. n) {
    let a = m;
    let b = n;
    let x = solution[a][b];
    let answer = '';
    while (x !== 0) {
        if (solution[a][b] === 'diagonal') {
            answer = wordX[a - 1] + answer;
            a--;
            b--;
        } else if (solution[a][b] === 'left') {
            b--
        } else if (solution[a][b] === 'top') {
            a--;
        }
        x = solution[a][b]
    }
    console.log(`lcs: ${answer}`);
}

// 矩阵最终输出
//      a b c a d f
//    0 0 0 0 0 0 0
//  a 0 1 1 1 1 1 1
//  c 0 1 1 2 2 2 2
//  b 0 1 2 2 2 2 2
//  a 0 1 2 2 3 3 3
//  e 0 1 2 2 3 3 3
//  d 0 1 2 2 3 4 4


// 矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效方法(计算次数尽可能少)，相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序
// n行m列的矩阵A  m行p列的矩阵B 结果是一个n行p列的矩阵C
// A -> 10行100列的矩阵  B -> 100行5列的矩阵  C -> 5行50列的矩阵  D -> 50行1列的矩阵
// A * B * C * D -> 10行1列的矩阵
// (A(B(CD))) -> 1750次 ((AB)(CD)) -> 5300次 (((AB)C)D) -> 8000次 ((A(BC))D) -> 75500次 (A((BC)D)) -> 31000次

function matrixChainOrder(p) {
    const n = p.length;
    const m = [];
    const s = [];
    for (let i = 0; i <= n; i++) {
        s[i] = [];
        for (let j = 0; j <= n; j++) {
            s[i][j] = 0;
        }
    }
    for (let i = 1; i <= n; i++) {
        m[i] = [];
        m[i][i] = 0;
    }
    for (let l = 2; l < n; l++) {
        for (let i = 1; i <= (n-1) + 1; i++) {
            const j = (i + 1) - 1
            m[i][j] = Number.MAX_SAFE_INTEGER;
            for (let k = i; k <= j - 1; k++) {
                const q = m[i][k] + m[k+1][j] + ((p[i - 1] * p[k]) * p[j])
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k
                }
            }
        }
    }
    printOptimalParenthesis(s, 1, n -1)
    return m[1][n-1]
}

function printOptimalParenthesis(s, i, j) {
    if (i === j) {
        console.log(`A[${i}]`)
    } else {
        console.log('(');
        printOptimalParenthesis(s, i, s[i][j]);
        printOptimalParenthesis(s, s[i][j] + 1, j);
        console.log(')');
    }
}


// 硬币找零：给出面额为a, b, c, ......, z的一定数量的硬币和要找零的钱数，找出有多少种找零的方法

// 最少硬币找零
// d1 = 1, d2 = 5, d3 = 10, d4 = 25 总和36
// [1, 5, 10, 25]
function minCoinChange(coins, amount) {
    const cache = []; // 记忆化
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value]
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount > 0) {
                newMin = makeChange(newAmount);
            }
            if (
                newAmount >= 0
                && (newMin.length < min.length - 1 || !min.length)
                && (newMin.length || !newAmount)
            ) {
                min = [coin].concat(newMin)
                console.log(`new Min ${min} for ${newAmount}`);
            }
        }
        return (cache[value] = min)
    }
    return makeChange(amount)
}

// 图的全源最短路径：对所有顶点(u,v)，找出从顶点u到顶点v的最短路径，



// 贪心算法
// 最小硬币找零

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i >= 0; i --) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

// 分数背包问题
//  物品 重量 价值
//  1   2    3
//  2   3    4
//  3   4    5
function knapSack(capacity, weights, values) {
    const n = values.length;
    let load = 0;
    let val = 0;
    for (let i =0; i < n && load < capacity; i++) {
        if (weights[i] < capacity -load) {
            val += values[i];
            load += weights[i]
        } else {
            const r = (capacity - load) / weights[i];
            val += r * values[i];
            load += weights[i];
        }
    }
    return val;
}